#include "treeBuild.h"
#include "math.h"
#include "treeStructure.h"
#ifndef NULL
#define NULL 0
#endif
// make a node at given location (x,y) and level
int addNum = 0;
int removeNum = 0;

Node *makeNode( double x, double y, int level ) {

  	int i;

  	Node *node = (Node *)malloc(sizeof(Node));

  	node->level = level;
  	node->flag = 0;
  	if (nodeValue(node,0.0)>0.5)
  		node->flag = 1;
  	else if (nodeValue(node,0.0)<-0.5)
  		node->flag = -1;

  	node->xy[0] = x;
  	node->xy[1] = y;

  	for( i=0;i<4;++i )
    	node->child[i] = NULL;

  	return node;
}

// split a leaf nodes into 4 children

void makeChildren( Node *parent ) {

  	double x = parent->xy[0];
  	double y = parent->xy[1];

  	int level = parent->level;
  	parent->flag = 0;

  	double hChild = pow(2.0,-(level+1));

  	parent->child[0] = makeNode( x,y, level+1 );
  	parent->child[1] = makeNode( x+hChild,y, level+1 );
  	parent->child[2] = makeNode( x+hChild,y+hChild, level+1 );
  	parent->child[3] = makeNode( x,y+hChild, level+1 );

  	return;
}

//Grow this tree

void growTree(Node *root,int i)
{
	if (i>root->level)
	{
		makeChildren(root);
		growTree(root->child[0],i);
		growTree(root->child[1],i);
		growTree(root->child[2],i);
		growTree(root->child[3],i);
	}
}

//Destory this tree

void destoryTree(Node * root)
{
    if(root != NULL)
    {
        for (int i=0;i<4;i++)
        {
            destoryTree(root->child[i]);
        }
        free(root);
    }
}

//Delete the leaves nodes

void removeChildren(Node * root)
{
	for (int i=0;i<4;i++)
	{
		free(root->child[i]);
		root->child[i] = NULL; 
	}
	root->flag = 0;
  	if (nodeValue(root,0.0)>0.5)
  		root->flag = 1;
  	else if (nodeValue(root,0.0)<-0.5)
  		root->flag = -1;
}

// Evaluate function at centre of quadtree node

double nodeValue( Node *node, double time ) {
	
	int level = node->level;
	double x = node->xy[0];
	double y = node->xy[1];
	
	double h = pow(2.0,-level);
	
	return( value( x+0.5*h, y+0.5*h, time ) );
}

// Data function

double value( double x, double y, double time ) {
	return( 2.0*exp(-8.0*(x-time)*(y-time)) - 1.0 );
}

void ChangeTreeByValue(Node* node)
{
	if (node->flag==0)
	{
		for (int i=0;i<4;i++)
		{
			if (node->child[i]->flag != -1)
				return;
		}
		removeChildren(node);
		removeNum+=4;
	}
	else if (node->flag == 1)
	{
		makeChildren(node);
		addNum+=4;
	}
}

void Adapt(Node*node)
{
	if (node->level>6)
		return;
	if (node->flag==0)
	{
		for (int i=0;i<4;i++)
		{
			Adapt(node->child[i]);
		}
	}
	ChangeTreeByValue(node);
}